// Created by WXX on 2021/11/15 11:43
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：140 ms, 在所有 C++ 提交中击败了35.39%的用户
 * 内存消耗：62.7 MB, 在所有 C++ 提交中击败了19.07%的用户
 */
typedef pair<int, int> PII;

#define x first
#define y second

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        vector<PII> ps[26];  // 存储每个字母 在哪个单词中出现 以及 该字母在单词中的位置
        for (int i = 0; i < words.size(); i++)
            ps[words[i][0] - 'a'].push_back({i, 0});  // (单词编号，当前指向该单词的位置)

        int res = 0;
        for (auto c : s) {
            vector<PII> buf;  // 缓存，防止出现读写冲突
            for (auto &p : ps[c - 'a']) {
                if (p.y + 1 == words[p.x].size()) res++;  // 说明单词words[p.x]匹配成功
                else buf.push_back({p.x, p.y + 1});
            }
            ps[c - 'a'].clear();
            for (auto &p : buf)
                ps[words[p.x][p.y] - 'a'].push_back(p);
        }
        return res;
    }
};

int main() {

    vector<string> words = {"a", "bb", "acd", "ace"};
    cout << Solution().numMatchingSubseq("abcde", words) << endl;  // 3

    return 0;
}
